
# 方法一：数学知识
class Solution:
    def twoEggDrop(self, n: int) -> int:
        ans=1
        # n 花多少步，能减到小于0
        while n>0:
            n-=ans
            ans+=1
        return ans-1

# 方法二：记忆化搜索 递归

class Solution:
    def twoEggDrop(self, n: int) -> int:
        # 导入 functools 模块中的 cache 装饰器，用于记忆化搜索
        from functools import cache

        # 定义一个递归函数 dfs，用于计算从 i 层楼开始测试所需的最少尝试次数
        @cache
        def dfs(i):
            # 如果楼层数为 0，不需要尝试，直接返回 0
            if i == 0:
                return 0
            # 初始化最小尝试次数为正无穷大
            min_attempts = float('inf')
            # 遍历从 1 到 i 的每一层楼，作为第一次扔鸡蛋的楼层
            for j in range(1, i + 1):
                # 假设在第 j 层扔鸡蛋，有两种情况：
                # 1. 鸡蛋碎了，此时只剩下一个鸡蛋，需要从第 1 层到第 j - 1 层逐层测试，即尝试次数为 j
                # 2. 鸡蛋没碎，此时还剩下两个鸡蛋，需要从第 j + 1 层到第 i 层继续测试，即尝试次数为 dfs(i - j) + 1  ，+1 为加上此前的操作
                # 取这两种情况中的最大值，因为要保证在最坏情况下也能找到答案
                attempts = max(j, dfs(i - j) + 1)
                # 更新最小尝试次数
                min_attempts = min(min_attempts, attempts)
            return min_attempts

        # 调用 dfs 函数，从第 n 层楼开始测试，返回最少尝试次数
        return dfs(n)


# 方法三： dp
# 初始化一个长度为 1001 的列表 f，用于存储不同楼层数下的最少尝试次数
# 初始值都设为 0，f[i] 表示有两枚鸡蛋且楼有 i 层时的最少尝试次数
f = [0] * 1001

# 从第 1 层开始，依次计算不同楼层数下的最少尝试次数
for i in range(1, len(f)):
    # 初始化当前楼层 i 对应的最少尝试次数为正无穷大
    # 后续会在循环中不断更新这个值，找到最小的尝试次数
    min_attempts = float('inf')
    # 遍历从 1 到 i 的每一层 j，模拟在第 j 层扔下第一枚鸡蛋的情况
    for j in range(1, i + 1):
        # 当在第 j 层扔下第一枚鸡蛋时，有两种情况：
        # 1. 鸡蛋碎了，此时只剩下一枚鸡蛋，需要从第 1 层到第 j - 1 层逐层测试，这种情况下尝试次数为 j
        # 2. 鸡蛋没碎，此时还剩下两枚鸡蛋，需要从第 j + 1 层到第 i 层继续测试，
        #    问题就转化为了有两枚鸡蛋且楼有 i - j 层的子问题，尝试次数为 f[i - j] + 1
        # 取这两种情况中的最大值，因为要考虑最坏情况
        attempts = max(j, f[i - j] + 1)
        # 更新当前楼层 i 对应的最少尝试次数
        min_attempts = min(min_attempts, attempts)
    # 将计算得到的最少尝试次数赋值给 f[i]
    f[i] = min_attempts

class Solution:
    def twoEggDrop(self, n: int) -> int:
        # 直接返回 f[n]，即有两枚鸡蛋且楼有 n 层时的最少尝试次数
        return f[n]